Channel coding provides significant improvements in communication systems which must operate in noisy environments. Consider a simple digital communication system in which messages consisting of sequences of bits are sent from a transmitter to a receiver. The transmission typically involves modulating a carrier signal with a waveform which specifies the value of the bit being sent. The output of the transmitter for a single bit will be referred to as the bit signal in the following discussion. In a binary transmission system, there are two such bit signals, one representing zero and the other representing one.
Upon reaching the receiver, the detected bit signals are compared with those corresponding to one and zero to recover each bit in the sequence. In a noisy environment, any bit signal may be corrupted by a noise pulse in its journey from the transmitter to the receiver. The probability of such a corruption is related to the statistical distribution of the noise pulses. In particular, it is related to the probability of finding a noise pulse which will add sufficient energy to the bit signal during transmission to corrupt that bit in a manner that will cause the receiver to mis-identify the bit signal.
It should be noted that the addition of a constant amount of energy to each bit signal need not cause corruption of the signal, as the receiver could compensate by subtracting a constant from each detected bit signal. Hence, the corruption results from adding different amounts of noise energy to different bit signals. The variation in the amount of energy added to each bit signal will depend on the duration of the bit signals. If the bit signals are long compared to the duration of the noise pulses, then the energy added to any given bit signal will be the average of the energies in a large number of noise pulses. Such an average will be relatively constant from bit signal to bit signal. If, however, the duration of the bit signals is of the same order as that of the noise pulses, the variation in added noise energy from bit signal to bit signal will be relatively large. Hence, it is advantageous to use relatively long bit signals.
If the bit signals do not overlap in time, such a strategy would result in a very low transmission bit rate on the communication channel. Such a reduction in transmission rate is generally to be avoided. Hence, a system in which the bit signals corresponding to adjacent bits in the message must overlap is desirable. The resultant transmission at any given time is the sum of the bit signals from a large number of bits.
The manner in which channel coding systems operate can be more easily understood with reference to a simple system for sending a message consisting of binary data over a communication channel. In this system, the bits of the message are replaced by bit signals which are then used to modulate a carrier. The bit signal for zero corresponds to the modulating sequence G[0,i] for i=0 . . . L-1, and the bit signal for one corresponds to the modulating sequence G[1,i] for i=0 . . . L-1. In the following discussion, "L" is generally used for the number of elements in the bit signal. A message comprising the sequence of bits b(j) is to be transmitted. It is assumed that the transmitter and receiver are clocked at a predetermined rate and that one message bit is introduced into the apparatus on each clock pulse. The transmitter includes L shift registers, each of length L. When a bit is to be transmitted, the appropriate bit signal is loaded into the next free shift register. On each clock pulse, all of the shift registers are shifted once, and the data which is shifted off of the end of each shift register is added to form the transmitted signal. The signal will then be a sequence .sigma.(k), where k denotes the clock pulse and ##EQU1## Here, G[p,i] is defined to be zero for i&lt;0 or i&gt;(L-1). In the absence of noise, the bits b(j) can be recovered at the receiver by circuitry that implements some method for solving an L.times.L system of linear equations. However, the computational workload involved makes this approach impractical for long waveforms.
If, however, the bit signals are orthogonal, the matrix representing the system of linear equations is diagonal, and the bits can be recovered by computing the correlation of the signal .sigma.(k) with the sequences G[1,i] and G[0,i]. If a bit having a value of B was sent starting at time K, then the correlation function ##EQU2## should be one for b=B and zero otherwise. It should be noted that the orthogonality requirement restricts the manner in which the message is sent. In particular, it can be shown that no finite sequence G[b,i] is orthogonal to itself shifted by an arbitrary integer, i.e., by an arbitrary multiple of a 1-unit shift. Hence, if orthogonal sequences are utilized, the data bits can, at most, be introduced into the transmitter on every other clock pulse.
Orthonormal bit signals have the additional advantageous property of being more immune to burst noise for a given length waveform. If non-orthonormal signals are used and .sigma.(k) is corrupted by a burst of noise at some time K, sufficient information may be lost to prevent correct demodulation of the signal to recover the message bits. If, however, orthonormal bit signals are utilized, the effect of the noise is to lower the correlation value for the correct bit value and increase the correlation for the incorrect bit value. Hence, provided the noise is not sufficient to make the correlation values corresponding to different bits indistinguishable, the signal can be recovered even in the presence of burst noise. Hence, orthonormal bit signals are preferred.
In addition to orthonormality, it is advantageous to utilize bit signals which have the property that the sum signal .sigma.(k) is statistically indistinguishable from the noise to within some tolerance. It can be shown that this requirement allows the system to utilize a greater fraction of the bandwidth of a noise channel for communication (C. Shannon "Communications theory of secrecy systems", Bell Systems Tech. Journal, 28 pp. 676-715, 1949).
This last property also provides a means for embedding a channel coded signal in the noise in a communication channel being used for other purposes. In addition to providing security for the information being transmitted, such a system may also be used to multiplex communications. For example, a channel coding system satisfying this condition could be used to send digital data on top of voice data in a telecommunication system. The digital data would merely appear as low power random noise. The extent to which background interference is found to be objectionable to human listeners depends greatly on the form of the interference. In particular, human listeners are less sensitive to random noise than to noise having a regular pattern. Hence, a significantly higher signal power may be used for the digital communication if the coded signal is indistinguishable from the typical static encountered on telephone lines.
While the basic features for such a system have been known for some time, no practical system meeting all of the conditions has been provided in the prior art. For example, Shannon proposed using two long sequences, G.sub.0 and G.sub.1, for the bit signals in which each sequence consists of numbers having a Gaussian pseudorandom distribution. It may be shown that two infinitely long random sequences are statistically orthonormal; however, pseudorandom sequences of finite length are not orthonormal in general.
Unfortunately, this suggested method has a number of problems. It should be noted that it is advantageous to be able to vary the length of the bit signals in response to the noise environment. When used to provide a reduction in noise errors, there is an optimal length for the bit signals. The computational load inherent in the correlation operation for decoding the signal at the receiver is related to the length of the bit signal. Hence, shorter bit signals are preferred. On the other hand, the ability to withstand noise interference improves with the length of the bit signal. However, there is a point at which doubling the length of the bit sequences results in only a small improvement in interference rejection. For example, if burst noise is the limiting characteristic of a communication channel, and if the bit signal is much longer in time than the average noise pulse, very little additional improvement is obtained by further increasing the size of the bit signal,
For given channel characteristics, the amount of information that can be sent over the channel depends on the length of the bit signal and specific values in the sequences. Before the signal .sigma.(k) can be decoded, it must be digitized at the receiver. For any given channel, there is a minimum signal variation that can be detected. The ratio of the maximum signal that can be accommodated in the channel to this minimum detectable signal variation will be referred to as the dynamic range of the channel. If the signal .sigma.(k) requires a greater dynamic range than the channel can accommodate, the signal will be clipped. Clipping can result in the loss of information.
Consider a system in which .sigma.(k) is used to modulate the amplitude of the carrier. As will be discussed in more detail below, the minimum dynamic range needed to accurately represent .sigma.(k) depends on the length of bit signals and the range of values contained in each bit signal. It can be seen from Eq. (1) that the dynamic range of .sigma.(k) depends on the dynamic range of the sequences G.sub.0 and G.sub.1, since the signal is itself a sum of values from these signals. In addition, the number of values to be combined depends on the length of the sequences. As the length of the sequences increases, the number of values to be combined, and hence, the required dynamic range, increases if data bits are to be sent in each available time interval. Hence, it is advantageous to employ bit signals that have as small a dynamic range as possible and to avoid excessively long sequences. Similar remarks apply to phase modulation, frequency modulation, and hybrid systems based on two or more of the above mentioned modulation techniques.
It is impossible to generate truly random signals of finite length. Pseudorandom sequences are known to the prior art; however, to satisfy the orthonormality conditions within a sufficient tolerance, the length of a pseudo-random sequence must be quite long. Hence, bit signals which are much longer than the optimum length must often be used if pseudo-random sequences are employed. Ideally one would like to be able to vary the length of the bit signals without altering the orthonormal character of the signals. No practical method for generating specified length sequences that appear random having this property is taught in the prior art.
In addition to the above mentioned problems, prior art systems are difficult to synchronize. Before a receiver can interpret the message sent by a transmitter, the transmitter and receiver must be synchronized. Initial synchronization is the most difficult to achieve. In long data transmissions, the receiver and transmitter must be periodically re-synchronized to correct for small differences in the frequencies of the clocks used in each device and/or drifts in the clock frequencies. In addition, changes in the distance between the transmitter and receiver can also lead to a loss of synchronization. Such changes in distance are encountered when one of the parties is utilizing mobile communications equipment such as a cellular telephone.
To achieve initial synchronization without using some form of non-channel sequence encoding, the phase of the receiver's clock is typically varied until a synchronization message is successfully decoded. The time needed to achieve initial synchronization is related to the length of the synchronization message and to the length of the bit signals used in the channel code. Hence, short synchronization messages and codes are preferred. However, the synchronization message must be long enough to guarantee that part of a valid message is not mistaken for a synchronization signal during the periodic re-synchronization procedures.
If non-channel encoded synchronization signals such as pilot tones are used, the power levels must be increased which can cause interference with other signals in the communication band. Such high power signals can be objectionable if the communication channel is being shared, as these signals would interfere with the other communications on the channel. In addition, in secure communication situations in which the user wishes to hide the fact that a communication is taking place, such high level signals can compromise the secrecy of the communication.
Broadly, it is an object of the present invention to provide an improved channel coding system.
It is a further object of the present invention to provide a channel coding codec utilizing orthonormal bit signals.
It is yet another object of the present invention to provide a channel coding system in which shorter synchronization signals than those used in prior art systems can be communicated without using non-spread spectrum codes and without being mistakenly interpreted by the receiver as part of a message.
It is a still further object of the present invention to provide a channel coding system in which the bit signals have the smallest possible dynamic range.
These and other objects of the present invention will be apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.